package lc.q201_250;

/**
 * 给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。
 *
 * @author lgb
 * @date 2020/08/23
 **/
public class Q201 {

    public int rangeBitwiseAnd(int m, int n) {
        // 按位与
        // 暴力解法
//        int result = m;
//        for (int i = m + 1; i < n; i++) {
//            // 思考，对于数来说，总共有31位（首位符号位不管）
//            // 如果任意一位是0，这个位可以不管后面的，就是0
//            // 再思考，m与n的公共前缀代表这范围内所有的公共前缀，而公共前缀的按位与是不变
//            // 后面肯定是0，因为公共前缀之后，肯定有位存在0的
//            result &= i;
//        }
//        return result;
//        int k = m;
//        int l = n;
//        // 如何求公共前缀？
//        int move = 0;
//        while (k < l) {
//            k = k >> 1;
//            l = l >> 1;
//            move ++;
//        }
//        // 得到公共前缀了
//        return l << move;

        // 另一种求公共前缀办法，
        // 就是每次n = n & (n-1)，消除最右边的1，直到n比m小
        while (m < n) {
            n = n & (n-1);
        }
        return n;
    }

}
